def select(nums,k):
    import random 
    p=random.choice(nums)
    a,b,c=[],[],[]
    for num in nums:
        if num<p:a.append(num)
        elif num==p:b.append(num)
        else:c.append(num)
    if len(a)>k: return select(a,k)
    elif len(a)+len(b)<k: return a+b+select(c,k-len(a)-len(b))
    else: return a+[p]*(k-len(a))

print(select([1,5,3,2,4,2,8],5))